1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to context adaptive binary arithmetic coding (CABAC), and more particularly, to a method of and apparatus for CABAC-encoding and CABAC-decoding a significance map indicating the positions of significant coefficients having non-zero value of a residual block.
2. Description of the Related Art
Since the amount of moving picture data is very large, moving picture data is usually compressed before it is stored or transmitted. There are a variety of methods of compressing data, and the compression of data should satisfy a predetermined standard. These standards include MPEG-4 Part 10 Advanced Video Coding (AVC) or ITU-T H.264. H.264 has been formulated in order to cope with rapid penetration of communication channels such as mobile communication networks, and is designed to enable a variety of communication infrastructures to switch from traditional circuit switching methods to packet switching services. Compared to MPEG-4 Part 2 Visual Codec, which is a previous standard, H.264 has improved encoding efficiency by 50% or more. H.264 is a video data compression standard which considers rapidly changing wireless environments and Internet environments, thereby reducing errors. H.264 also considers network adaptive methods.
H.264 uses context adaptive binary arithmetic coding (CABAC) which is an arithmetic coding technique with enhanced compression efficiency. The CABAC is an entropy encoding method of compressing data by using probabilities of symbols.
FIG. 1 is a block diagram illustrating an apparatus for CABAC according to conventional technology. In an encoding process according to H.264, a discrete cosine transform is performed in units of residual blocks, each of which has a size of 4×4, and then, a syntax element is generated in relation to each 4×4 residual block.
Referring to FIG. 1, the CABAC encoding apparatus according to the conventional technology broadly includes a binarizer 10, a context modeler 20, and a binary arithmetic coder 30. Also, the arithmetic coder 30 includes a regular coding engine 32 and a bypass coding engine 34.
If a non-binary valued syntax element is input, the binarizer 10 maps the syntax element into a sequence of binary values, thereby outputting a bin string.
In order to increase the processing speed of the encoding process, the bin string obtained by mapping into binary values by the binarizer 10 or predetermined bin values selected from a syntax element having binary values therein is encoded by the bypass coder 34 without being input to the context modeler 20, and is output as a bitstream. Other bins are input to the context modeler 20. Here, a bin indicates each bit of a bin string.
Based on the input bin values or a previously encoded syntax element, the context modeler 20 determines a probability model required for encoding a currently input bin.
The regular coding engine 32 arithmetic-encodes the input bin value, based on the probability model determined in the context modeler 20, and generates a bitstream.
According to the H.264 standard draft, a block which is currently encoded is classified into one of roughly five types as illustrated in table 1 below, and in order to encode a syntax element in relation to a block belonging to each type, a different context is applied:
TABLE 1# ofBlock typescoeff.Context TypeLuminance DC block for INTRA16 ×160: Luma-Intra16-DC16 modeLuminance AC block for INTRA16 ×151: Luma-Intra16-AC16 modeLuminance block for INTRA 4 × 4 mode162: Luma-4 × 4Luminance block for INTER mode16U-Chrominance DC block for INTRA mode43: Chroma-DCV-Chrominance DC block for INTRA mode4U-Chrominance DC block for INTER mode4V-Chrominance DC block for INTER mode4U-Chrominance AC block for INTRA mode154: Chroma-ACV-Chrominance AC block for INTRA mode15U-Chrominance AC block for INTER mode15V-Chrominance AC block for INTER mode15
In the encoding process according to H.264, DCT and quantization is performed in units of 4×4 residual blocks, and then, a syntax element of residual data is generated in relation to each 4×4 residual block. Syntax elements of the 4×4 residual block defined in H.264 includes coded_block_flag, significant_coeff_flag[i], and coeff_sign_flag[i].
FIG. 2 is a flowchart illustrating a process of encoding residual data according to conventional technology.
Referring to FIG. 2, in operation 210, coded_block_flag, which indicates whether or not a non-zero coefficient value exists among 16 quantized coefficients of a current 4×4 residual block, is encoded. In a given residual block, if the coded_block_flag is 0, it means that no information to be transmitted exists. According to the H.264 standard draft, a context which is used in the encoding of the coded_block_flag of the current residual block is determined by using context information which is used for encoding adjacent blocks of the same type as that of the current residual block, positioned above and to the left of the current residual block.
In operation 220, if a non-zero coefficient value (hereinafter referred to as a significant coefficient) exists in the current 4×4 residual block, a significance map indicating the position of the significant coefficient is encoded. The significance map is formed with significant bits and an end-of-block (EOB). A significant bit indicates whether a coefficient according to each scan index is a significant coefficient or 0, and is expressed by significant_coeff_flag[i]. Here, significant_coeff_flag[i] indicates whether or not the coefficient value of an i-th scan index among 16 coefficients of a 4×4 residual block is 0.
FIGS. 3A and 3B are diagrams illustrating a significance map of a 4×4 residual block according to conventional technology.
Referring to FIG. 3A, it is assumed that coefficients at the positions marked by X among coefficients in the 4×4 residual block 31 have predetermined non-zero values. In this case, as illustrated in FIG. 3B, a significance map 32 is obtained by expressing each significant coefficient among the coefficients in the 4×4 residual block as 1, and each insignificant coefficient having zero value as 0. The significance map is scanned in a predetermined scan order, and thus context-based arithmetic encoding is performed. For example, in the case of raster scanning in which contents are scanned from the left-hand side to the right-hand side, and from the top to the bottom, when the significance map as illustrated in FIG. 3A is encoded, a bin string of  is context-based encoded. In order to encode a significance map, 15 different probability models are used for significant_coeff_flag and last_significant_coeff_flag. A context used for encoding a significance map is determined according to a scanning position of a predetermined scan order. That is, according to the conventional technology, when the significance map as illustrated in FIG. 3B is encoded, a context to be used for encoding is determined according to the position of each coefficient.
Referring again to FIG. 2, in operation 230, level information of a significant coefficient, i.e., the sign and absolute value (abs) of the significant coefficient is encoded. In respect of image encoding efficient, it is known that the performance of the CABAC is generally better than the performance of context adaptive variable length coding (CAVLC). The overhead of the CAVLC is about 10˜15% more than that of the CABAC.
FIG. 4 is a graph illustrating the performance difference between the CABAC and the CAVLC with respect to a variety of quantization parameter values according to conventional technology. FIG. 4 illustrates the incremental amount of overhead when the symbols and texture of an image sequence (football CIF) are encoded by using the CAVLC, with reference to the amount of overhead occurring when the same symbols and texture of the image are encoded by using the CABAC. The symbol (♦) indicates the amount of overhead which increases when the symbols of the image sequence (football CIF) are encoded by using the CAVLC, compared to the CABAC, and the symbol (▪) indicates the amount of overhead which increases when the texture of the image sequence (football CIF) is encoded by using the CAVLC, compared to the CABAC.
Referring to FIG. 4, when texture is encoded, the amount of overhead occurring when the CAVLC is used greatly increases compared to that of the CABAC, with the increasing quantization parameter (QP) value. However, when the QP value is low, there is no big difference between the overhead occurring when the CABAC is used, and the overhead occurring when the CAVLC is used. Referring to FIG. 4, for example, when the QP value is 24, the incremental amount of overhead when texture is encoded by using the CAVLC is mere 3%. In other words, when the value of a QP value is small, i.e., when the picture quality of an image is good, the encoding performance of the CABAC is relatively decreased.
One of the reasons why the encoding performance of the CABAC is decreased in a low QP is inefficiency of context modeling of a significance map indicating the positions of significant coefficients.
FIG. 5 is a graph illustrating probabilities of significant coefficients in each scan index occurring when a significance map of a 4×4 residual block is encoded according to conventional technology. FIG. 6 is a graph illustrating probabilities of insignificant coefficients in each scan index occurring when a significance map of a 4×4 residual block, with respect to changes in quantization parameter values according to conventional technology. FIG. 5 illustrates the probability of a significant coefficient of each scan index when QP=24 and a significance map of a 4×4 residual block of a Football QCIF image is scanned according to a raster scan order. FIG. 6 illustrates the probability that an insignificant coefficient, i.e., a coefficient which is 0, occurs in each scan index when a significance map of a 4×4 residual block of a BUS CIF image in relation to each of when QP=24, when QP=30, and when QP=34. Here, a scan index is an index indicating the position of each coefficient of a 4×4 residual block according to the scanning order. For example, scan index 1 indicates the position of a coefficient of a direct current (DC) component positioned at the first column of the first line of a 4×4 residual block.
Referring to FIG. 5, in some scan indexes such as the second and fifth scan indexes, the probability of a significant coefficient and the probability of an insignificant coefficient are both about 50%, and similar to each other. Referring to FIG. 6, with the decreasing QP value, coefficients around a DC component, in particular, for example, in the first, fifth and ninth scan indexes, the probability difference between a significant coefficient and an insignificant coefficient becomes relatively small.
Thus, according to the conventional technology, in some scan indexes, probabilities of insignificant coefficients and significant coefficients are set to similar values. That is, when a significance map is encoded, a context is set according to a scan index, and in a probability model according to the selected context, the probabilities of a most probable symbol  and a least probable symbol  in a certain scan index can be set to values similar to each other. The performance of the CABAC is lowered when the probabilities of an MPS and an LPS are similar to each other. This is well known. Accordingly, in order to make the difference between probabilities of an MPS and an LPS greater when a context for encoding a significance map is selected, a method of more efficiently performing context modeling is needed.